package com.cat.monotonicStack;

import java.util.ArrayList;
import java.util.List;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/next-greater-node-in-linked-list/
 * @create 2025/8/13 14:28
 * @since JDK17
 */

public class Solution02 {
    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    static int N = ((int) (1e4 + 10)), top;
    static int[][] stack = new int[N][2];

    public int[] nextLargerNodes(ListNode head) {
        int cnt = 0;
        top = 0;
        for (ListNode p = head; p != null; p = p.next) {
            cnt++;
        }
        int[] ans = new int[cnt];
        for (ListNode p = head; p != null; p = p.next) {
            while (top > 0 && p.val > stack[top - 1][0]) {   // 小压大
                ans[stack[--top][1]] = p.val;
            }
            stack[top][0] = p.val;
            stack[top++][1] = cnt++;
        }
        return ans;
    }
}
